package com.wujunshen.algorithm.leetcode.dynamic.programming;

/**
 * 这个题总共就两种状态：1.当天有股票 2.当天没股票。这里我们使用二维数组 dp[prices.length][2] 来记录每天的两种状态。例如：dp[0][0]代表第一天手里没有股票，dp[0][1]代表手里有股票。
 * <p>
 * 我们要求的是每天手里有股票和没有股票的最大利润，下面我给大家分开讨论：
 * <p>
 * 当天没有股票dp[i][0]这支股票有两种可能：
 * <p>
 * 昨天就没有股票：dp[i - 1][0]
 * 昨天有股票，今天卖了:dp[i - 1][1] + prices[i]
 * 当天有股票dp[i][1]这支股票有两种可能：
 * <p>
 * 昨天的股票在手里没卖出去： dp[i - 1][1]
 * 昨天没有股票了，今天刚买,刚买的时候，手里本来是没钱的（没钱的原因是因为本题要求只能有一次股票交易），所以是dp[i - 1][0] - prices[i] = 0 - prices[i] = -prices[i]
 * 最后返回最后一天手里没股票的时候的最大利润即可，也就是 dp[prices.length - 1][0]
 * <p>
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/8/9 14:30<br>
 */
public class 买卖股票的最佳时机 {
    public int maxProfit(int[] prices) {
        //两个状态：手里没股票，手里有股票
        int dp0 = 0;
        int dp1 = Integer.MIN_VALUE;
        for (int price : prices) {
            //手里没股票
            dp0 = Math.max(dp0, dp1 + price);
            //手里有股票
            dp1 = Math.max(dp1, -price);
        }
        //返回没股票的时候
        return dp0;
    }
}
